package own.stu.jobgib.playown.alg.leetcode.editor.cn;

//爱丽丝有一手（hand）由整数数组给定的牌。 
//
// 现在她想把牌重新排列成组，使得每个组的大小都是 W，且由 W 张连续的牌组成。 
//
// 如果她可以完成分组就返回 true，否则返回 false。 
//
// 
//
// 注意：此题目与 1296 重复：https://leetcode-cn.com/problems/divide-array-in-sets-of-k-co
//nsecutive-numbers/ 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 
//输入：hand = [1,2,3,6,2,3,4,7,8], W = 3
//输出：true
//解释：爱丽丝的手牌可以被重新排列为 [1,2,3]，[2,3,4]，[6,7,8]。 
//
// 示例 2： 
//
// 
//输入：hand = [1,2,3,4,5], W = 4
//输出：false
//解释：爱丽丝的手牌无法被重新排列成几个大小为 4 的组。 
//
// 
//
// 提示： 
//
// 
// 1 <= hand.length <= 10000 
// 0 <= hand[i] <= 10^9 
// 1 <= W <= hand.length 
// 
// Related Topics Ordered Map 
// 👍 98 👎 0


import java.util.Map;
import java.util.TreeMap;

public class HandOfStraights{
    public static void main(String[] args) {
        Solution solution = new HandOfStraights().new Solution();
        System.out.println(solution.isNStraightHand(new int[]{1,2,3,6,2,3,4,7,8}, 3));
        System.out.println(solution.isNStraightHand(new int[]{1,2,3,4,5}, 4));
        System.out.println(solution.isNStraightHand(new int[]{1,1,2,2,3,3}, 3));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isNStraightHand(int[] hand, int W) {
            if(hand == null || hand.length % W != 0){
                return false;
            }
            Map<Integer, Integer> map = new TreeMap<>();
            for(int i : hand){
                map.put(i, map.getOrDefault(i, 0) + 1);
            }

            for(Map.Entry<Integer, Integer> entry : map.entrySet()){
                Integer key = entry.getKey();
                Integer value = entry.getValue();
                if(value == 0){
                    continue;
                }
                if(value < 0){
                    return false;
                }
                for(int i = 0; i < W; i ++){
                    if(map.get(key + i) != null){
                        map.put(key + i, map.get(key + i) - 1 * value);
                    }else{
                        return false;
                    }
                }
            }

            return true;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
